package main

import (
	"fmt"
	"math"
)

/*
	题目4：求数组中的大两倍对数量

题目描述：
在一个数组中，
对于每个数num，求有多少个后面的数 * 2 依然<num，求总个数

比如：[3,1,7,0,2]
3的后面有：1，0
1的后面有：0
7的后面有：0，2
0的后面没有
2的后面没有
所以总共有5个
*/
func main() {
	arr := []int{8, 3, 3, 10, 5, 10, 6}

	fmt.Println(arr)
	res := MergeSort3(arr)

	fmt.Println(arr, res)
}
func MergeSort3(arr1 []int) int {
	if arr1 == nil && len(arr1) < 2 {
		return 0
	}

	N := len(arr1)
	mergeSize := 1
	L := 0
	res := 0
	for true {
		L = 0
		for L < N {
			Mid := L + mergeSize - 1
			if Mid >= N {
				break
			}
			R := int(math.Min(float64(Mid+mergeSize), float64(N-1)))
			fmt.Println(L, Mid, R)
			res += Merge3(arr1, L, Mid, R)
			L = R + 1
		}
		if mergeSize > N/2 {
			break
		}
		mergeSize <<= 1
	}
	return res
}

func Merge3(arr []int, l, mid, r int) int {

	res := 0
	windowR := mid + 1
	for i := 0; i <= mid; i++ { //这是一个一次性找完不需要回退的技巧
		for windowR <= r && arr[i] > arr[windowR]*2 { //只要arr[i]当前的位置的值大于windowR当前的位置的值说明后续的arr[i]就肯定大于windowR之前的数
			windowR++ //如果遇到arr[i]大于当前的windowR位置的数就让其windowR++就行如果windowR>r说明当前的左组i的位置就已经大于所有右组的数了就不用for循环判断右组边界了
		}
		res += windowR - mid - 1 //累加 所以windowR每次可以直接加但是要减去mid和1 这边稍微想一下就明白了了
	}

	help := make([]int, r-l+1)

	p1 := l
	p2 := mid + 1
	i := 0

	for p1 <= mid && p2 <= r {

		if arr[p1] < arr[p2] {
			help[i] = arr[p1]

			p1++
			i++
		} else if arr[p2] < arr[p1] {
			help[i] = arr[p2]
			//if arr[p2]*2 < arr[p1] {
			//	res += mid - p1 + 1 //核心代码只有当p2小于p1时p1剩余所有数都能和当前p2这个数构成逆序对
			//}
			p2++
			i++

		} else {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p2 > r {

		for p1 <= mid {
			help[i] = arr[p1]
			p1++
			i++
		}
	}

	if p1 > mid {

		for p2 <= r {
			help[i] = arr[p2]
			p2++
			i++
		}
	}

	for i, v := range help {
		arr[l+i] = v

	}
	return res

}
